import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public int reverse(int x) {
        char[] chars = String.valueOf(x).toCharArray();
        char tmp;
        int start = 0;
        if(chars[0] == '-'){
            start = 1;
        }
        /**
         * 如果为负数，索引从1开始，则char[i]=char[chars.length-i];
         * 如果为正数，索引从0开始，则char[i]=char[chars.length-1-i];
         * 格式化数字
         * 如果为负数，-12300，-321
         * 如果为正数，12300，321
         */
        int le = (chars.length % 2 == 0) ? chars.length / 2 : (chars.length / 2 + 1);
        for (int i = start; i < le; i++) {
            tmp= chars[i];
            chars[i] = chars[chars.length-(1-start)-i];
            chars[chars.length-(1-start)-i] = tmp;
        }
        String value = String.valueOf(chars);
        // 如果反转后整数超过 32 位的有符号整数的范围 ，就返回 0。
        char[] maxArry = String.valueOf(0x7fffffff).toCharArray();
        char[] minArry = String.valueOf(0x80000000).toCharArray();
        if(value.contains("-")){
            if(chars.length>minArry.length){
             return 0;
            }else if(chars.length==minArry.length){
                for (int i=1;i<chars.length;i++){
                    if(chars[i]<minArry[i]) break;
                    else if (chars[i]==minArry[i]) continue;
                    else return 0;
                }
            }
        }else {
            if(chars.length>maxArry.length){
                return 0;
            }else if(chars.length==maxArry.length){
                for (int i=0;i<chars.length;i++){
                    if(chars[i]<maxArry[i]) break;
                    else if(chars[i]==maxArry[i]) continue;
                    else return 0;
                }
            }
        }
        int parseInt = Integer.parseInt(value);
        return parseInt;
    }
    //回文数判断
    public boolean isPalindrome(int x) {
        if(x<0) return false;
        if(x<=9) return true;
        char[] chars = String.valueOf(x).toCharArray();
        int len = (chars.length%2==0)?chars.length/2:(chars.length/2+1);
        for (int i = 0; i < len; i++) {
            if(chars[i] == chars[chars.length-1-i]) continue;
            else return false;
        }
        return true;
    }
    //罗马数字转整型
    /*
        字符          数值
        I             1
        V             5
        X             10
        L             50
        C             100
        D             500
        M             1000
    I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
    X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
    C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900
     */
    public int romanToInt(String s) {
        String[] split = s.split("");
        HashMap<String, Integer> romaMap = new HashMap<>();
        romaMap.put("I",1);
        romaMap.put("IV",4);
        romaMap.put("V",5);
        romaMap.put("IX",9);
        romaMap.put("X",10);
        romaMap.put("XL",40);
        romaMap.put("L",50);
        romaMap.put("XC",90);
        romaMap.put("C",100);
        romaMap.put("CD",400);
        romaMap.put("D",500);
        romaMap.put("CM",900);
        romaMap.put("M",1000);
        int sum=0;
        for (int i = 0; i < split.length; i++) {
            Integer integer = null;
            if(i<split.length-1){
                integer = romaMap.get(String.valueOf(split[i]) + split[i + 1]);
            }
            if(null == integer){
                integer = romaMap.get(String.valueOf(split[i]));
                System.out.println(String.valueOf(split[i]));

            }else {
                System.out.println(String.valueOf(split[i]+split[i+1]));
                i++;
            }
            sum+=integer;
        }
        return sum;
    }
    //最长公共前缀
    public String longestCommonPrefix(String[] strs) {
        String substring = "";
        if(strs.length==0) return substring;
        if(strs.length==1) return strs[0];
        for (int i = 0; i < strs[0].length(); i++) {
            substring = strs[0].substring(0, i+1);
            for (int j = 0; j < strs.length; j++) {
                if(strs[j].startsWith(substring)) continue;
                else return strs[0].substring(0,i);

            }
        }
        return substring;
    }
    //有效括号
    /*
        给定一个只包括 '(',')','{','}','[',']' 的字符串 s ，判断字符串是否有效。
     */
    public boolean isValid(String s) {
        List<Character> start = Arrays.asList('(', '[', '{');
        List<Character> end = Arrays.asList(')', ']', '}');
        char[] array = s.toCharArray();
        ArrayList<Character> list = new ArrayList<>();
        ArrayList<Boolean> booleans = new ArrayList<>();
        ArrayList<Integer> integers = new ArrayList<>();
        for (char c1 : array) {
            if(start.contains(c1)){
                list.add(c1);
                booleans.add(false);
            }
            if(end.contains(c1)){
                list.add(c1);
                booleans.add(false);
//                integers.add(list.size()-1);
            }
        }
        if(list.size()%2==1) return false;
        int left=0,right=0,index=0;
        for (int i = 0; i < list.size(); i++) {
            if(end.contains(list.get(i))){
                right=i;
                for (int j = i-1; j >= 0; j--) {
                    index +=1;
                    boolean contains = start.contains(list.get(i - j).charValue());
                    Boolean aBoolean = booleans.get(i - j);
                    if(start.contains(list.get(i-j).charValue()) && !booleans.get(i-j)){
                        if (start.indexOf(list.get(i-index).charValue())!=end.indexOf(list.get(i).charValue())){
                            System.out.println("sssssssssss");
                            return false;

                        }else break;
                    }else{
                        continue;
                    }

                }
                booleans.set(i,true);
                booleans.set(i-index,true);
            }else{
            }
                index=0;
        }
        for (Boolean aBoolean : booleans) {
            if(!aBoolean){
                System.out.println("bbbbbbbbbbbb");
                return false;
            }
        }
        return true;
    }
    //外观数列
    public String countAndSay(int n) {
        String str = "1";
        for (int i = 1; i < n; i++) {
            str = count(str);
        }
        return str;
    }
    public String count(String str){
        int num=0;
        char[] chars = str.toCharArray();
        char ch = ' ';
        StringBuffer buffer = new StringBuffer("");
        for (int i=0;i<chars.length;i++) {
            if(i == 0){
                ch = chars[i];
                num = 1;
            }else {
                if(ch!=chars[i]){
                    buffer.append(num+String.valueOf(ch));
                    num = 1;
                    ch = chars[i];
                }else{
                    ++num;
                };

            }
            if(i==chars.length-1) buffer.append(num+String.valueOf(ch));
        }
        return buffer.toString();
    }
    //平方根
    /*
        取中值，平方看大小，如果大，取中值的中值，否则取中值与该值的一半
        如果相等则返回，如果两侧相差为一，则返回较小值。否则继续上一步
     */
    public int mySqrt(int x) {
        int tmp=46340;
        if(tmp*tmp<=x) return tmp;
        int length = String.valueOf(x).length();
        if(x==0 || x==1) return x;
        if(x<0) return 0;
        int min = 0,max=1;
        int l = length%2==0?(length/2):(length/2+1);
        for (int i = 0; i < l; i++) {
            max = max*10;
        }
        max = max>tmp?tmp:max;
        while ((max-min)!=1){
            int mid=(min+max)/2;
            if(mid*mid>x){
                max=mid;
            }else if(mid*mid==x) return mid;
            else{
                min=mid;
            }
        }
        System.out.println(tmp*tmp);
        System.out.println(x);
        return min;
    }
    //最大子序和
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) return nums[0];
        int max=nums[0],sum=0;
        for (int i = 0; i < nums.length; i++) {
            sum = nums[i];
            for (int j = i; j < nums.length; j++) {
                if(j==i){
                    sum = nums[j];
                }else {
                    sum = sum+nums[j];
                }
                max = max>=sum?max:sum;
            }
        }
        return max;
    }
    //最后一个单词的长度
    public int lengthOfLastWord(String s) {
        String[] s1 = s.split(" ");
        if(s1.length == 0) return 0;
        ArrayList<String> list = new ArrayList<>();
        for (String s2 : s1) {
            if(!" ".equals(s2)) list.add(s2);
        }
        return list.get(list.size()-1).length();
    }
    //加一
    public int[] plusOne(int[] digits) {
        int a = 0;
        int[] arr= null;
        for (int i = digits.length-1; i >=0 ; i--) {
            if(i== digits.length-1) a=1;
            int s = digits[i]+a;
            if(i==0 && s>9){
                    arr = new int[digits.length+1];
                    arr[0] = s/10;
                    for (int j = 0; j < digits.length; j++) {
                        arr[j+1] = s%10;
                    }
                return arr;
            }
            if(s > 9){
                a=s/10;
            }else{
                a=0;
            }
            digits[i] = s%10;
        }
        return digits;
    }
    //二进制求和
    public String addBinary(String a, String b) {
        char[] aChars = a.toCharArray();
        char[] bChars = b.toCharArray();
        StringBuffer sumBuffer = new StringBuffer("");
        int tmp=0;
        int len = aChars.length>bChars.length?aChars.length:bChars.length;
        for (int i = 0; i < len; i++) {
            int aIn=0,bIn=0;
            if(i<aChars.length && aChars[aChars.length-i-1]=='1'){
                aIn=1;
            }
            if(i<bChars.length && bChars[bChars.length-i-1]=='1'){
                bIn=1;
            }
            sumBuffer.insert(0,(aIn+bIn+tmp)%2);
            tmp=(aIn+bIn+tmp)/2;
        }
        if(tmp!=0) sumBuffer.insert(0,tmp);
        return sumBuffer.toString();
    }
    //爬楼梯   每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶
    public int climbStairs(int n) {
        int num=0;
        climbStep(n);
        return num;
    }
    public int climbStep(int climb){
        System.out.println(climb);
        for (int i = 1; i <= 2; i++) {
            if(climb==i){
                System.out.println("===");
                continue;
            };
            if(climb>i){
                climb-=i;
                int climbStep = climbStep(climb);
                if(climbStep ==-1){
                    continue;
                }
            }else {
                break;
            }
        }
        return -1;
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
           if(l1 == null) return l2;
           if(l2==null) return l1;
           ListNode node = l1;
           if(l1.next == null){
               if(l1.val<l2.val){
                   l1.next = l2;
               }else {
                   ListNode node1 = null;
                   if(l2.next != null){
                       node1  = new ListNode(l2.next.val,l2.next.next);
                   }
                   l2.next = l1;
                   l1 = l2;
                   l2 = node1;
               }
           }
           while (l1.next.val<l2.val){
               node = l1.next;
           }
           ListNode node1 = new ListNode(node.val,node.next);
           l2.next = node1;
           node.next = l2;
           return mergeTwoLists(l1,l2.next);

    }
    public void sayListNode(ListNode listNode){
        while (listNode!=null){
            System.out.print(listNode.val+",");
            listNode = listNode.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        boolean valid = solution.isValid("(){}[[]]");
        System.out.println(valid);
       /* ListNode a1 = new ListNode(5);
        ListNode a2 = new ListNode(2);
        ListNode a3 = new ListNode(4);
        ListNode b1 = new ListNode(1);
        ListNode b2 = new ListNode(2);
        ListNode b3 = new ListNode(4);
//        a1.next=a2;
//        a2.next=a3;
        b1.next=b2;
        b2.next=b3;
        ListNode listNode = solution.mergeTwoLists(a1, b1);
        solution.sayListNode(listNode);*/
    }
}
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
